package com.cdream.basic.algorithm.leetcode.sort;

/**
 * todo 桶排序还有一个方法
 * @author cdream
 * @date 5/11/21
 */
public class Question75 {
    public void sortColors(int[] nums) {
        // 0是第一个不是0的位置/第一个1元素
        int zero = 0; // nums[0...zero）都是0
        // two是结束的位置
        int two = nums.length-1; // nums(two,n-1] 都是2
        for (int i = 0; i <= two; ) {
            // 0 和 1进行交换
            if (nums[i] == 0) {
                swap(nums, zero++, i++);
            } else if (nums[i] == 2) {
                swap(nums, two--, i);
            } else {
                i++;
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
